package binaryTree;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

/**
 * 判断所给定的二叉树是不是完全二叉树，如果是，将存储结构转换为顺序存储
 * */
public class CompleteBT<AnyType extends Comparable<? super AnyType>> {
	//存储转换为顺序存储的完全二叉树
	public AnyType[] a;

	/**
	 * 判断所给定的二叉树是不是完全二叉树
	 * */
	public boolean isCompleteBT(BTNode<AnyType> root) {
		boolean result = true;
		int tag=0;

		if (root == null) {
			System.out.println("该树为空树！");
			return false;
		}
		// 初始化一个队列
		Queue queue = new ArrayDeque<BTNode>();

		// 把根节点加入到队列中,因为Queue继承了Collection方法
		queue.add(root);
		
		// 当该队列不为空时
		while (!queue.isEmpty()) {
			
			BTNode<AnyType> temp = (BTNode) queue.poll();
			
			// 按照层次加入到队列中
			if (temp.getLeftChild() != null && tag==0) {

				queue.add(temp.getLeftChild());
			}else if(temp.getLeftChild()!=null){//前面已有结点为空，本结点不空
				return false;
			}else{
				tag=1;//首次出现节点为空
			}
			if (temp.getRightChild() != null && tag==0) {
				queue.add(temp.getRightChild());
			}else if(temp.getRightChild() != null){//前面已有结点为空，本结点不空
				return false;
			}else{
				tag=1;//首次出现节点为空
			}

		}
		return result;
	}

	/**
	 * 将完全二叉树存储结构,转换为顺序存储
	 * @param root 根节点
	 * @param a 大小为节点数目的数组
	 * */
	public AnyType[] change2ArrayStorage(BTNode<AnyType> root,AnyType[] a) {
		if (root == null){
			return null;
		}
		//初始化一个队列
		Queue queue = new ArrayDeque<BTNode>();
		//把根节点加入到队列中,因为Queue继承了Collection方法
		queue.add(root);
		int i=0;
		//当该队列不为空时
		while (!queue.isEmpty()) {
			
			BTNode<AnyType> temp = (BTNode) queue.poll();
			a[i]=(AnyType) temp.getData();
			//按照层次加入到队列中
			if (temp.getLeftChild() != null) {
				queue.add(temp.getLeftChild());
			}
			if (temp.getRightChild()!= null){
				queue.add(temp.getRightChild());
			}
			i++;
		}
		return a;
	}

	/**
	 * 将完全二叉树转换顺序存储后，判断是不是堆
	 * */
	public boolean isHeap(AnyType[] a) {
		
		if(a[0].compareTo(a[1]) >= 0){
			for(int i=0;i<a.length-1;i++){
				//大顶堆
				if(a[i].compareTo(a[i+1])>=0){
					continue;
				}else{
					return false;
				}
			}
			System.out.println("该序列是大顶堆");
		}else{
			for(int i=0;i<a.length-1;i++){
				//小顶堆
				if(a[i].compareTo(a[i+1])<=0){
					continue;
				}else{
					return false;
				}
			}
			System.out.println("该序列是小顶堆");
		}
		
		return true;
	}

	/**
	 * 若不是堆，将其调整为堆，并输出结果检查调整后的结果是否正确
	 * */
	public void change2Heap(AnyType[] a) {
		HeapSort h=new HeapSort();
		h.heapsort(a);
		
		System.out.println("排序的最后结果为：");
		for(int j=0;j<a.length;j++){
			System.out.print(a[j]+"\t");
		}
	}

	// 测试函数
	public static void main(String[] args) {
		BinaryTree bt1 = new BinaryTree();
		Scanner in = new Scanner(System.in);
		System.out.println("请输入字符串，以先序的顺序创建创建二叉树：");
		// 非完全二叉树供测试数字串 ：abd   ce  f  
		// 完全二叉树：dba  e  cf   
		String str = in.nextLine();
		/** 将字符串转换成字符数组 */
		char[] tree = str.toCharArray();
		/** 创建包装类的数组 */
		Character[] preOrder = new Character[tree.length];
		/** 遍历数组，景数组中非空格的字符包装后，存入包装类数组，对空格字符赋值为null */
		for (int i = 0; i < tree.length; i++) {
			if (tree[i] == ' ') {
				preOrder[i] = null;
			} else {
				// preOrder[i]=new Character(tree[i]);
				preOrder[i] = tree[i];
			}
		}
		/** 创建二叉树 */
		bt1.setNode(((BinaryTree) bt1).createBTByPreOrder(preOrder));
		

		CompleteBT c = new CompleteBT();
		boolean t= c.isCompleteBT(bt1.getNode());
		System.out.println("该二叉树是否为完全二叉树？（true/false）");
		System.out.println(t);
		
		Character[] a=new Character[bt1.countNode()];
		
		//将存储结构转换为顺序存储
		if(t){
			System.out.println("该完全二叉树的顺序存储结果为：");
			System.out.println("");
			a=(Character[]) c.change2ArrayStorage(bt1.getNode(), a);
			for(int i=0;i<a.length;i++){
				System.out.print(a[i]+"   ");
			}
			System.out.println("");
			
			//若是完全二叉树，将其转换为顺序存储后，判断是不是堆
			System.out.println("判断该完全二叉树是否为堆？（true/false）");
			boolean h=c.isHeap(a);
			System.out.println(h);
			if(!h){
				//将其调整为堆，并输出结果检查调整后的结果是否正确
				c.change2Heap(a);
			}
		}
	}
}
